| comments | difficulty | edit_url |
|---|---|---|
true | 简单 |
颜色填充。编写函数，实现许多图片编辑软件都支持的“颜色填充”功能。给定一个屏幕（以二维数组表示，元素为颜色值）、一个点和一个新的颜色值，将新颜色值填入这个点的周围区域，直到原来的颜色值全都改变。
示例1:
输入： image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2 输出：[[2,2,2],[2,2,0],[2,0,1]] 解释: 在图像的正中间，(坐标(sr,sc)=(1,1)), 在路径上所有符合条件的像素点的颜色都被更改成2。 注意，右下角的像素没有更改为2， 因为它不是在上下左右四个方向上与初始点相连的像素点。
说明：
- image 和 image[0] 的长度在范围 [1, 50] 内。
- 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
- image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。
我们设计一个函数
时间复杂度
classSolution: deffloodFill( self, image: List[List[int]], sr: int, sc: int, newColor: int ) ->List[List[int]]: defdfs(i, j): if ( not0<=i<mornot0<=j<norimage[i][j] !=ocorimage[i][j] ==newColor ): returnimage[i][j] =newColorfora, binpairwise(dirs): dfs(i+a, j+b) dirs= (-1, 0, 1, 0, -1) m, n=len(image), len(image[0]) oc=image[sr][sc] dfs(sr, sc) returnimageclassSolution { privateint[] dirs = {-1, 0, 1, 0, -1}; privateint[][] image; privateintnc; privateintoc; publicint[][] floodFill(int[][] image, intsr, intsc, intnewColor) { nc = newColor; oc = image[sr][sc]; this.image = image; dfs(sr, sc); returnimage; } privatevoiddfs(inti, intj) { if (i < 0 || i >= image.length || j < 0 || j >= image[0].length || image[i][j] != oc || image[i][j] == nc) { return; } image[i][j] = nc; for (intk = 0; k < 4; ++k) { dfs(i + dirs[k], j + dirs[k + 1]); } } }classSolution { public: vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) { int m = image.size(), n = image[0].size(); int oc = image[sr][sc]; int dirs[5] = {-1, 0, 1, 0, -1}; function<void(int, int)> dfs = [&](int i, int j) { if (i < 0 || i >= m || j < 0 || j >= n || image[i][j] != oc || image[i][j] == newColor) { return; } image[i][j] = newColor; for (int k = 0; k < 4; ++k) { dfs(i + dirs[k], j + dirs[k + 1]); } }; dfs(sr, sc); return image; } };funcfloodFill(image [][]int, srint, scint, newColorint) [][]int { oc:=image[sr][sc] m, n:=len(image), len(image[0]) dirs:= []int{-1, 0, 1, 0, -1} vardfsfunc(i, jint) dfs=func(i, jint) { ifi<0||i>=m||j<0||j>=n||image[i][j] !=oc||image[i][j] ==newColor { return } image[i][j] =newColorfork:=0; k<4; k++ { dfs(i+dirs[k], j+dirs[k+1]) } } dfs(sr, sc) returnimage }functionfloodFill(image: number[][],sr: number,sc: number,newColor: number): number[][]{constdfs=(i: number,j: number): void=>{if(i<0||i>=m){return;}if(j<0||j>=n){return;}if(image[i][j]!==oc||image[i][j]===nc){return;}image[i][j]=nc;for(letk=0;k<4;++k){dfs(i+dirs[k],j+dirs[k+1]);}};constdirs: number[]=[-1,0,1,0,-1];const[m,n]=[image.length,image[0].length];constoc=image[sr][sc];constnc=newColor;dfs(sr,sc);returnimage;}implSolution{fndfs(i:usize,j:usize,target:i32,new_color:i32,image:&mutVec<Vec<i32>>){if image[i][j] != target {return;} image[i][j] = new_color;if i != 0{Self::dfs(i - 1, j, target, new_color, image);}if j != 0{Self::dfs(i, j - 1, target, new_color, image);}if i + 1 != image.len(){Self::dfs(i + 1, j, target, new_color, image);}if j + 1 != image[0].len(){Self::dfs(i, j + 1, target, new_color, image);}}pubfnflood_fill(mutimage:Vec<Vec<i32>>,sr:i32,sc:i32,new_color:i32) -> Vec<Vec<i32>>{let(sr, sc) = (sr asusize, sc asusize);let target = image[sr][sc];if target == new_color {return image;}Self::dfs(sr, sc, target, new_color,&mut image); image }}classSolution{privatevardirs=[-1,0,1,0,-1]privatevarimage:[[Int]]=[]privatevarnc:Int=0privatevaroc:Int=0func floodFill(_ image:inout[[Int]], _ sr:Int, _ sc:Int, _ newColor:Int)->[[Int]]{self.nc = newColor self.oc =image[sr][sc]self.image = image dfs(sr, sc)returnself.image }privatefunc dfs(_ i:Int, _ j:Int){if i <0 || i >= image.count || j <0 || j >=image[0].count || image[i][j]!= oc || image[i][j]== nc {return}image[i][j]= nc forkin0..<4{dfs(i + dirs[k], j + dirs[k +1])}}}我们可以使用广度优先搜索的方法，从起始点开始，将起始点的颜色填充成新的颜色，然后将起始点加入队列。每次从队列中取出一个点，然后将其上下左右四个方向的点加入队列，直到队列为空。
时间复杂度
classSolution: deffloodFill( self, image: List[List[int]], sr: int, sc: int, newColor: int ) ->List[List[int]]: ifimage[sr][sc] ==newColor: returnimageq=deque([(sr, sc)]) oc=image[sr][sc] image[sr][sc] =newColordirs= (-1, 0, 1, 0, -1) whileq: i, j=q.popleft() fora, binpairwise(dirs): x, y=i+a, j+bif0<=x<len(image) and0<=y<len(image[0]) andimage[x][y] ==oc: q.append((x, y)) image[x][y] =newColorreturnimageclassSolution { publicint[][] floodFill(int[][] image, intsr, intsc, intnewColor) { if (image[sr][sc] == newColor) { returnimage; } Deque<int[]> q = newArrayDeque<>(); q.offer(newint[] {sr, sc}); intoc = image[sr][sc]; image[sr][sc] = newColor; int[] dirs = {-1, 0, 1, 0, -1}; while (!q.isEmpty()) { int[] p = q.poll(); inti = p[0], j = p[1]; for (intk = 0; k < 4; ++k) { intx = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < image.length && y >= 0 && y < image[0].length && image[x][y] == oc) { q.offer(newint[] {x, y}); image[x][y] = newColor; } } } returnimage; } }classSolution { public: vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) { if (image[sr][sc] == newColor) return image; int oc = image[sr][sc]; image[sr][sc] = newColor; queue<pair<int, int>> q; q.push({sr, sc}); int dirs[5] = {-1, 0, 1, 0, -1}; while (!q.empty()) { auto [a, b] = q.front(); q.pop(); for (int k = 0; k < 4; ++k) { int x = a + dirs[k]; int y = b + dirs[k + 1]; if (x >= 0 && x < image.size() && y >= 0 && y < image[0].size() && image[x][y] == oc) { q.push({x, y}); image[x][y] = newColor; } } } return image; } };funcfloodFill(image [][]int, srint, scint, newColorint) [][]int { ifimage[sr][sc] ==newColor { returnimage } oc:=image[sr][sc] q:= [][]int{[]int{sr, sc}} image[sr][sc] =newColordirs:= []int{-1, 0, 1, 0, -1} forlen(q) >0 { p:=q[0] q=q[1:] fork:=0; k<4; k++ { x, y:=p[0]+dirs[k], p[1]+dirs[k+1] ifx>=0&&x<len(image) &&y>=0&&y<len(image[0]) &&image[x][y] ==oc { q=append(q, []int{x, y}) image[x][y] =newColor } } } returnimage }functionfloodFill(image: number[][],sr: number,sc: number,newColor: number): number[][]{if(image[sr][sc]===newColor){returnimage;}constq: number[][]=[[sr,sc]];constoc=image[sr][sc];image[sr][sc]=newColor;constdirs: number[]=[-1,0,1,0,-1];while(q.length){const[i,j]=q.pop()!;for(letk=0;k<4;++k){const[x,y]=[i+dirs[k],j+dirs[k+1]];if(x>=0&&x<image.length&&y>=0&&y<image[0].length&&image[x][y]===oc){q.push([x,y]);image[x][y]=newColor;}}}returnimage;}